package com.example.demo.leetcode.top100;

import java.util.Arrays;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _99下一个排列
 * @description
 * @date 2023/07/04 14:45
 * <p>
 * ******************************************************
 */
public class _99下一个排列 {


    /**
     * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
     * <p>
     * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
     * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。
     * 更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，
     * 那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。
     * 如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
     * <p>
     * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
     * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
     * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
     * 给你一个整数数组 nums ，找出 nums 的下一个排列。
     * <p>
     * 必须 原地 修改，只允许使用额外常数空间。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,3]
     * 输出：[1,3,2]
     * 示例 2：
     * <p>
     * 输入：nums = [3,2,1]
     * 输出：[1,2,3]
     * 示例 3：
     * <p>
     * 输入：nums = [1,1,5]
     * 输出：[1,5,1]
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 100
     *
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        // 什么是字典序
//        1.字典序全排列问题
//
//        示例：1 2 3的全排列如下：
//
//        1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1
//        我们这里是通过字典序法找出来的。
//        那么什么是字典序法呢？
//
//        从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？
//
//        我们再来看一段文字描述：（用字典序法找124653的下一个排列）
//
//        如果当前排列是124653，找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数
//        如果找不到，则所有排列求解完成，如果找得到则说明排列未完成
//        本例中将找到46，计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数
//        本例找到的数是5，其位置计为j，将i与j所在元素交换125643
//        然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列



        // 设计思路：

        // 1.从数组右侧向左开始遍历，找是否存在nums[i]>nums[i-1]的情况，

        // 2.如果不存在这种nums[i]>nums[i-1]情况 ，for循环会遍历到i==0（也就是没有下一个排列），
        // 此时按题意排成有序Arrays.sort()

        // 3.如果存在，则将从下标i到nums.length()的部分排序，
        // 然后在排过序的这部分中遍历找到第一个大于nums[i-1]的数，并与nums[i-1]交换位置


        int length = nums.length;
        for (int i = length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, length);
                for (int j = i; j < length; j++) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }

        // 如果找不到
        Arrays.sort(nums);
    }

}
